#pragma once

#include <string>
#include <utility>
#include <vector>

namespace solution_079
{

class Solution
{
public:
    bool exist(std::vector< std::vector<char> >& board, std::string word)
    {
        m_rows = board.size();
        m_cols = board.front().size();
        m_board = &board;
        m_word.swap(word);

        for (int i = 0; i < m_rows * m_cols; ++i) {
            int r = i / m_cols;
            int c = i % m_cols;
            if (board[r][c] == m_word.front()) {
                int current_len = 1;
                board[r][c] *= -1;
                if (backtrack(current_len, i))
                    return true;
                board[r][c] *= -1;
            }
        }
        return false;
    }

private:
    bool backtrack(int& current_len, int current)
    {
        if (current_len == (int)m_word.size())
            return true;

        const auto next_ch = m_word.at(current_len);
        const int row = current / m_cols;
        const int col = current % m_cols;

        for (auto& step : conn4) {
            auto r = row + step.first;
            auto c = col + step.second;
            auto next = r * m_cols + c;
            if ( r >= 0 && r < m_rows && c >= 0 && c < m_cols && next_ch == m_board->at(r).at(c) ) {
                m_board->at(r).at(c) *= -1;
                ++current_len;
                if (backtrack(current_len, next))
                    return true;
                --current_len;
                m_board->at(r).at(c) *= -1;
            }
        }

        return false;
    }

    int m_rows = 0;
    int m_cols = 0;

    std::vector< std::vector<char> >* m_board;
    std::string m_word;

    inline static const std::pair<int, int> conn4[] = { {0,-1}, {0,1}, {-1,0}, {1,0} };
};

}  /* namespace solution_079 */
